//
//  main.c
//  C_Study
//
//  Created by rui on 12-8-28.
//  Copyright (c) 2012年 Wang Rui. All rights reserved.
//



/*
 @要点：链式树:处理思想，每个子节点都是一个子树，每一个树想成三个部分：根节点，左子树，又子树
	   源码6-2.h部分
 */

#include "types.h"

#define CHAR 0

#if CHAR
	typedef char TElemType;
	#define Nil ' '
	#define form "%c"
#else
	typedef int TElemType;
	#define Nil 0
	#define form "%d"
#endif


typedef struct BiTNode
{
	TElemType data;
	struct BiTNode *lchild,*rchild; /* 左右孩子指针 */
}BiTNode,*PBiTNode;


/**********************************/
/*@链式存储二叉树基本操作            */
/**********************************/

void initBiTree(BiTNode **pt)
{
	*pt = NULL;
}

void creatBiTree(BiTNode **pt){
	TElemType in;
	scanf(form,&in);
	
	if (in == Nil) 
	{
		*pt = NULL;
	} 
	else 
	{
		*pt = (BiTNode *)malloc(sizeof(BiTNode));
		if(NULL == *pt)
			exit(OVERFLOW);
		(*pt)->data = in;
		creatBiTree(&(*pt)->lchild);
		creatBiTree(&(*pt)->rchild);
	}
}

void destroyTree(BiTNode **pt){
	if (*pt != NULL) {
		destroyTree(&(*pt)->lchild);
		destroyTree(&(*pt)->rchild);
		free(*pt);
		*pt = NULL;
	}
}

bool is_empty(PBiTNode node)
{
	return  node == NULL;
}

int biTreeDepth(PBiTNode node)
{
	if (NULL == node) 
		return 0;
	int i,j;
	
	i = biTreeDepth(node->lchild);
    j = biTreeDepth(node->rchild);
	
	return i>j? i+1:j+1;
}

int nodeSumCount(PBiTNode node)
{
	if (NULL == node) {
		return 0;
	}
	
	int sl,sr;
	
	sl = nodeSumCount(node->lchild);
	sr = nodeSumCount(node->rchild);
	
	return sl+sr+1;
}

//返回T的根
TElemType root(PBiTNode node)
{
	if (is_empty(node)) {
		return Nil;
	}
	else {
		return node->data;
	}
}

void assign(PBiTNode p,TElemType value)
{ /* 给p所指结点赋值为value */
	p->data=value;
}

TElemType value(PBiTNode p)
{ /*操作结果：返回p所指结点的值 */
	return p->data;
}


/*
 *以下三个寻找节点相关函数书上是以队列的形式实现
 */

/*找到某一节点的值*/
TElemType findBiNodeValue(PBiTNode root,PBiTNode e)
{
	if (root == NULL) {
		return Nil;
	}
	
	int ret;
	
	if (root == e) 
	{
		return root->data;
	}
	else 
	{
		ret = findBiNodeValue(root->lchild, e);
			if(ret != Nil)
				return ret;
		ret = findBiNodeValue(root->rchild, e);
			if(ret != Nil)
				return ret;
	}
	
	return Nil;
}

/*根据值找到某一节点*/
PBiTNode findBiNode(PBiTNode root,TElemType e)
{
	if (root == NULL) {
		return NULL;
	}
	
	PBiTNode ret;
	
	if (root->data == e) 
	{
		return root;
	}
	else 
	{
		ret = findBiNode(root->lchild, e);
		if(ret != NULL)
			return ret;
		ret = findBiNode(root->rchild, e);
		if(ret != NULL)
			return ret;
	}
	
	return NULL;
}

/*根据值找到父一节点*/ 
PBiTNode find_parentNode(PBiTNode root,TElemType e)
{
	if (root == NULL) {
		return NULL;
	}
	
	PBiTNode ret;
	
	if (root->lchild != NULL && root->rchild != NULL && 
		(root->lchild->data == e || root->rchild->data == e)) 
	{
		return root;
	}
	else 
	{
		ret = find_parentNode(root->lchild, e);
		if(ret != NULL)
			return ret;
		ret = find_parentNode(root->rchild, e);
		if(ret != NULL)
			return ret;
	}
	
	return NULL;
}

/*根据节点值找到父节点值*/ 
TElemType parent(PBiTNode T,TElemType e)
{
	if (NULL == T) {
		return Nil;
	}
	
	PBiTNode p = find_parentNode(T, e);
	if (p != NULL) {
		return p->data;
	}
	
	return Nil;
}


TElemType LeftChild(PBiTNode T,TElemType e)
{
	PBiTNode p = findBiNode(T, e);
	if (NULL!=p && NULL!=p->lchild) 
	{
		return p->lchild->data;
	}
	return Nil;
}

TElemType RightChild(PBiTNode T,TElemType e)
{
	PBiTNode p = findBiNode(T, e);
	if (NULL!=p && NULL!=p->lchild) 
	{
		return p->rchild->data;
	}
	return Nil;
}

TElemType LeftSibling(PBiTNode T,TElemType e)
{
	PBiTNode p = find_parentNode(T, e);
	if (p != NULL && NULL != p->lchild) {
		return p->lchild->data;
	}
	
	return Nil;
}


/* 初始条件：二叉树T存在，p指向T中某个结点，LR为0或1，非空二叉树c与T不相交且右子树为空 */
/* 操作结果：根据LR为0或1，插入c为T中p所指结点的左或右子树。p所指结点的原有左或右子树则成为c的右子树 */
Status insertChild(PBiTNode p,int LR,PBiTNode c)
{
	if (NULL == p) {
		return ERROR;
	}
	
	if (LR == 0) {//left
		PBiTNode t = p->lchild;  
		p->lchild = c;
		c->lchild = t;
	}
	else {
		c->rchild = p->rchild;
		p->rchild = c;
	}
	
	return OK;
}

Status DeleteChild(PBiTNode p,int LR){
	
	if (NULL != p) {
		if (LR == 0) {
			destroyTree(&p->lchild);
		}
		else
			destroyTree(&p->rchild);
		return OK;
	}
	
	return ERROR;
}


/*
 *遍历算法 （中序可采取栈的方法遍历）
 */
typedef void (* VisitFuc)(TElemType);

void preTravel(PBiTNode node, VisitFuc visit)
{
	if (node != NULL) {
		visit(node->data);
		preTravel(node->lchild, visit);
		preTravel(node->rchild, visit);
	}
}

void inTravel(PBiTNode node, VisitFuc visit)
{
	if (node != NULL) {
		inTravel(node->lchild, visit);
		visit(node->data);
		inTravel(node->rchild, visit);
	}
	
}

void postTravel(PBiTNode node, VisitFuc visit)
{
	if (node != NULL) {
		postTravel(node->lchild, visit);
		postTravel(node->rchild, visit);
		visit(node->data);
	}
}


/**********************************/
/*@辅助函数						  */
/**********************************/

void visit(TElemType e)
{
	printf(form,e);
}

/**********************************/
/* @main函数                       */
/**********************************/
int main(int argc, const char * argv[])
{
	BiTNode *p = NULL;
	initBiTree(&p);
	creatBiTree(&p);
	
//	preTravel(p, visit);
//	inTravel(p, visit);
//	postTravel(p, visit);
	
//	printf("levels:%d\n",biTreeDepth(p));
//	printf("nodes:%d\n",nodeSumCount(p));
//	TElemType t = parent(p, 5);
//	printf("find:%d\n",t);
	
	return 0;
}

